The present invention relates in general to the problem of tracking one or more objects over time, and in particular to the problem of assigning reports from one or more sensors to tracks across multiple observation periods. It also relates to the problem of tracking multiple features on a moving elastic or inelastic object(s).
In a typical application, a tracker receives a stream of reports over time from one or more sensors (such as a radar), each of which may indicate either the detection of an actual object of interest (or closely spaced group of such objects) or a false alarm. The objects of interest may include, for example, aircraft, missiles, ships or land vehicles. The tracker may also be used to track particular points on an organ of an organism, in medical imaging applications.
The problem of assigning reports is to determine which reports correspond to which objects. For a tracker dealing with many reports collected across some time period (such that each real object may have generated two or more reports from observations at different times), the number of different ways of combining these reports into tracks (or tracks and false alarms) can grow very large. Each possible combination is called a hypothesis.
The problem of assigning reports involves searching for an optimal or near optimal hypothesis according to a metric specific to the tracker in question. In the general case, finding the optimal hypothesis for more than a small number of objects observed over time (such that each real object may have generated several reports from observations at different times) is impractical due to the high computational expense required. Therefore, suboptimal search techniques are usually employed.
Without loss of generality, we may describe the problem of assigning reports as if the sensor reports arrived in groups where each report in the group was collected over the same time period (called a "scan"). The problem of searching for an optimal or near optimal hypothesis across multiple scans is different in character from searching for the best hypothesis for the associations between reports from one scan and a set of tracks. In general, finding the local optimal assignment of objects (targets) to tracks for each scan does not guarantee that the global optimal assignment across many scans is achieved. Multi-scan, multiple target algorithms commonly used include Multi-Hypothesis Trackers (MHTs). See, for example, D. B. Reid, IEEE Transactions on Automatic Control (December 1979), pp. 843 to 854; S. S. Blackman, Multiple Target Tracking with Radar Applications (Artech House, Dedham, Mass., 1986).
A Genetic Algorithm (GA) is an artificial intelligence technique based loosely on the process of natural selection in evolutionary biology. See, for example, D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley, Reading, Mass., 1989); J. Holland, Adaptation in Natural and Artificial Systems (University of Michigan Press, 1975); Z. Michalkawicz, Genetic Algorithms+Data Structures=Evolution Programs (Springer-Verlag, Berlin, 1992). The Genetic Algorithm has wide applications in optimization, intelligent search, and machine learning. See, for example, N. L. Ulder, et al, Genetic Local Search Algorithms for the Traveling Salesman, Parallel Problem Solving from Nature, 1st Workshop, Springer-Verlag, October 1990; H. C. Braun, On Solving Travelling Salesman Problems by Genetic Algorithms, Parallel Problem Solving from Nature, 1st Workshop, Springer-Verlag, October 1990; G. von Lawszewski, H. Muhlenbein, Partitioning a Graph with a Parallel Genetic Algorithm, Parallel Problem Solving from Nature, 1st Workshop, Springer-Verlag, October 1990.
To apply a GA, a problem is generally expressed in such a way that potential solutions can be encoded as character strings over some alphabet. Most commonly, these character strings are binary strings, but other representations such as matrices and computer program listings can be applied. Then, a population of potential solutions called "individuals" is formed. Each individual is decoded, tested against some metric and scored. A new population is then formed by mutation (small random changes) and recombination (forming a new individual using material from a pair of parent individuals). Individuals with high scores or fitnesses are selected to be parents with a higher probability than others. The new population is then decoded and scored and the process repeated until some end condition is reached.
A genetic algorithm is NOT a succession of random searches for highly fit individuals. As the adage goes, "genes use people to make copies of themselves". What a GA really processes are substrings (not necessarily contiguous) within the individuals' character strings called "schemata".
Using the biological metaphor, an individual's string is its genotype (each character is one gene), the expressed parameter values are its phenotype, and a schema (any pattern of particular character values in particular places in the bit string) is a combination of genes. The entire string is the genotype, a substring is a schema.
A "good schema" is one that is expressed to form some subset of the solution that confers an advantage to the individual. A "good schema" will, on the average, tend to occur in individuals with relatively high fitness values. These individuals will be selected more frequently as parents and will, in turn, produce more offspring containing that schema.
Over a few generations, the gene pool of the population changes as good schemata crowd out lesser ones. New schemata are constantly formed and evaluated. Some of the new schemata will crowd out previously successful schemata. Over time, individuals are formed from better schemata and tend to have higher fitness values. Of course, not all problems are compatible with this technique. An assumption of the technique is that, at least sometimes, schemata that are good in other contexts will remain good when combined.
While an individual represents just one total solution, the number of schemata it contains is equal to the number of (not necessarily contiguous) substrings of its bit string. By sampling a relatively small number of individuals over several generations, a GA can process a huge number of schemata. This inherent parallelism is key to the effectiveness of GAs.
A paper entitled "Multiple target tracking data association using a genetic algorithm", by Carrier, Leung, Lo, Litva, of McMaster Univ. Canada, was presented at the SPIE conference in Orlando in April 1996. The paper is in "SPIE Proceedings Vol. 2739". The approach of Carrier et al is to use a GA on the single scan problem to search for the best association between a list of detections and a list of tracks. The method of Carrier et al cannot easily be extended to the multiple scan case.
U.S. Pat. No. 5,793,931, issued on Aug. 11, 1998 (the "'931 patent") and having the same inventor as the present application, discloses a related multi-sensor multi-target tracking invention and is hereby incorporated by reference.